package com.song.boot.springstudy.sort;

import java.util.Arrays;

/**
 * 快速排序算法实现类
 * 采用分治法思想，以首元素作为基准进行分区
 */
public class QuickSort {

    /**
     * 测试方法
     */
    public static void main(String[] args) {
        // 测试数组
        int[] testArray = {25, 6, 4, 10, 1, 3, 20, 27};
        System.out.println("排序前的数组: " + Arrays.toString(testArray));

        // 执行快速排序
        quickSort(testArray);

        // 输出排序结果
        System.out.println("排序后的数组: " + Arrays.toString(testArray));
    }

    /**
     * 快速排序入口方法
     * @param arr 待排序的数组
     */
    public static void quickSort(int[] arr) {
        // 边界检查：如果数组为空或长度小于2，则无需排序
        if (arr == null || arr.length < 2) {
            return;
        }
        // 调用递归排序方法，初始范围为整个数组
        quickSort(arr, 0, arr.length - 1);
    }

    /**
     * 递归实现快速排序
     * @param arr 待排序的数组
     * @param low 当前排序区间的起始索引
     * @param high 当前排序区间的结束索引
     */
    private static void quickSort(int[] arr, int low, int high) {
        // 递归终止条件：当起始索引大于等于结束索引时，子数组已排序完成
        if (low >= high) {
            return;
        }

        // 进行分区操作，获取基准元素的最终位置
        int pivotIndex = partition(arr, low, high);

        // 递归排序基准元素左侧的子数组
        quickSort(arr, low, pivotIndex - 1);
        // 递归排序基准元素右侧的子数组
        quickSort(arr, pivotIndex + 1, high);
    }

    /**
     * 分区操作：将数组分为两部分，左侧元素小于基准，右侧元素大于基准
     * @param arr 待分区的数组
     * @param low 分区的起始索引
     * @param high 分区的结束索引
     * @return 基准元素的最终索引位置
     */
    private static int partition(int[] arr, int low, int high) {
        // 选择首元素作为基准值
        int pivot = arr[low];
        
        // 左指针：从基准元素的下一个位置开始
        int left = low + 1;
        // 右指针：从数组的最后一个元素开始
        int right = high;

        // 循环直到左右指针相遇或交叉
        while (left <= right) {
            // 左指针向右移动，找到第一个大于基准值的元素
            while (left <= right && arr[left] <= pivot) {
                left++;
            }

            // 右指针向左移动，找到第一个小于等于基准值的元素
            while (left <= right && arr[right] > pivot) {
                right--;
            }

            // 如果左右指针未交叉，则交换对应位置的元素
            if (left < right) {
                swap(arr, left, right);
            }
        }

        // 将基准元素与右指针指向的元素交换，使基准元素归位
        swap(arr, low, right);

        // 返回基准元素的最终索引位置
        return right;
    }

    /**
     * 交换数组中两个位置的元素
     * @param arr 要操作的数组
     * @param i 第一个元素的索引
     * @param j 第二个元素的索引
     */
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


}
    